嗨咪納桑，咱是immortalmice，今天要來和各位分享自己研究出的幾個新資料結構

這個資料結構支援以下五個操作

1. Random Get (隨機存取)
2. Push (尾端插入)
3. Pop (尾端移除)
4. Unshift (首端插入)
5. Shift (首端移除)

乍看之下，好像就是一個支援隨機存取的雙端佇列
用陣列手刻一個實作出來一點也不難，那我的資料結構究竟是為了什麼而誕生呢
而這就要提到各位修資料結構的課時都被教過的效能問題

• 動態陣列(DynamicArray)在隨機存取表現優秀，但SHIFT & UNSHIFT表現差
• 雙向連結串列(DoublyLinkedList)在雙端插入移除表現優異，但隨機存取表現差

因此，本研究在尋找一個可以融合兩者優點的類陣列資料結構

首先，來些東西鎮樓
這是本研究的Repo，裡面包含了Javascript和Java的語言實作以及效能測試報告
(貼心提醒所有的README都有中文喔 >.0)
至於測試報告，舉例來說這是Java語言實作的AdaptiveArray的測試報告，其他的可以在README中找到
從圖表中可以看到，不管在哪種操作的組合測試中，我的資料結構雖然不是永遠的第一名，但他絕不會是最後一名
這證明了我的研究成功地融合了動態陣列和雙向連結串列的優點 而不是融合缺點

至於為何可以做到這樣，這邊我歸類出三個最重要的研究方向

1. 讓此資料結構同時擁有動態陣列和雙向連結串列的特徵，試圖獲得兩個資料結構的優勢
2. 用Push操作取代Unshift，避免因插入而移動陣列內既有的元素，並用一個可以為負的index為元素紀錄順序關係
3. 用一個特殊的Refactor機制整理元素，讓被整理好的元素在被隨機存取時可以更快被找到，同時也加快尋找未被整理元素的動作

在研究過程中，生出了三個資料結構

• LinkArray是最初的一位，包含了上面的三個研究方向，成功的獲得了兩個資料結構的優勢
• AutoLinkArray，在LinkArray中，refactor是影響效能很重要的一個動作，但基於懶人思想，此資料結構會基於策略在自認適合的情況下自動執行refactor的動作，免去了手動執行的功夫
• AdaptiveArray，在測試AutoLinkArray的報告中發現它在陣列內容物少時不具有優勢，因此最後的這個資料結構以動態陣列作為初始實作，當陣列長度大於一定程度時自動轉換為AutoLinkArray的實作

至於更詳細的實作細節，可以觀看Repo的README或已經實作出來的兩個語言的程式碼，這邊不再重複一次

最後，關於Contribution
這是一個開源的專案，希望可以獲得大大您的幫助

1. 對於本資料結構的意見
   雖然已經查過很多次都沒發現有人在做一樣的事
   但如果你知道遠在天邊的另一個研究有在做類似的事情，請不吝告訴我，讓我了解
   或是你有改進本資料結構的意見也歡迎提出
2. 新的語言的實作
   除了Java和Javascript之外，本Repo歡迎提供其他的語言實作，請發PR給我，也歡迎透過站內簡訊和我討論
3. 實作的benchmarking程式碼和效能測試報告
   現在的Java和Javascript效能測試是由我手工撰寫，但本人也不是這方面的專長
   更何況實作和測試都由我寫可能有些裁判兼球員的味道在，因此也歡迎新的benchmarking程式碼和效能測試報告
   可以發PR給我，也歡迎透過站內簡訊和我討論

最後謝謝看到這裡的你，本鼠下台一鞠躬